package cengxubianli

import (
	"fmt"
	"hufeng/ercahshu"
	"math"
)

func minDepth(root *ercahshu.TreeNode) int {
	if root == nil {
		return 0
	}
	var ans int
	queue := make([]*ercahshu.TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		n := len(queue)
		ans++
		for i := 0; i < n; i++ {
			node := queue[i]
			if node.Left == nil && node.Right == nil {
				return ans
			}
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		queue = queue[n:]
	}
	return ans
}

func digui(root *ercahshu.TreeNode) int {
	// 使用后序遍历进行处理
	ans := math.MaxInt32
	var dfs func(node *ercahshu.TreeNode, n int)
	dfs = func(node *ercahshu.TreeNode, n int) {
		if node == nil {
			return
		}
		if node.Left == nil && node.Right == nil {
			ans = min(ans, n)
			return
		}
		dfs(node.Left, n+1)
		dfs(node.Right, n+1)
	}
	dfs(root, 0)
	fmt.Println(ans)
	return ans
}
